/**
 * 
 */
package leetCode;

/**
 * @author zhongfang
 *
 */
public class FindtheDerangementofAnArray {
    public static int findDerangement(int n) {
    	int mod=1000000007;
    	if(n<3){
            return n-1;
        }
    	long[] dp=new long[n+1];
    	dp[1]=0;
    	dp[2]=1;
    	for (int i = 3; i < dp.length; i++) {
			dp[i]=(i-1)*((dp[i-1]+dp[i-2])%mod)%mod;
		}
        return (int) dp[n];
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(findDerangement(3));
	}

}
